#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
using namespace std;

//207.课程表
bool canFinish(int numCourses, vector<vector<int>>& prerequisites){
    // 用哈希表来表示邻接表
    // key值表示一个节点，val表示一个数组，里面存放的是key值节点指向的下一个节点
    // key=0;val=[1,2,3];表示0指向1，2，3三个节点
    unordered_map<int, vector<int>> edges;
    //用数组来存放每个节点的入度,本道题中下标正好对应节点
    vector<int> in(numCourses);

    //建图
    for(auto& nums : prerequisites){
        //[a,b]表示b->a,在完成a之前先完成b
        int a = nums[0], b = nums[1];

        //b->a,存放b的下一个节点
        edges[b].push_back(a);
        //节点a入度+1
        in[a]++;
    }

    //将入度为0的入队
    queue<int> q;
    for (int i = 0; i < in.size(); i++){
        if(in[i]==0){
            q.push(i);
        }
    }

    //拓扑排序
    while(!q.empty()){
        //获取队头节点并出队
        int t = q.front();
        q.pop();

        //遍历当前下标对应的所有下一个节点，将对应的节点入度-1，表示删除指向的边
        for(auto num : edges[t]){
            in[num]--;
            //如果对应节点的入度为0，入队
            if(in[num]==0){
                q.push(num);
            }
        }
    }

    //遍历入度数组，如果出现某个节点的入度不为0说明存在环,不能遍历所有节点
    for (auto num : in){
        if(num==1){
            return false;
        }
    }

    return true;
}

//210.课程表2
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites){
    //本道题是上一道的变形，具体过程一模一样

    //用哈希表表示邻接表，数组存放每个节点的入度
    unordered_map<int, vector<int>> edges;
    vector<int> in(numCourses);

    //建表
    for(auto& e : prerequisites){
        //b->a
        int a = e[0], b = e[1];
        edges[b].push_back(a);
        in[a]++;
    }

    //将所有入度为0的入队
    queue<int> q;
    for (int i = 0; i < in.size(); i++){
        if(in[i]==0){
            q.push(i);
        }
    }

    //建立一个数组用来返回最终的结果
    vector<int> ret;

    //拓扑排序，bfs实现
    while(!q.empty()){
        //获取队头节点并出队
        int t=q.front();
        q.pop();

        ret.push_back(t);

        //通过当前节点遍历所有指向的节点
        for(auto num : edges[t]){
            //修改指向的节点的入度
            in[num]--;
            //如果入度为0，入队
            if(in[num]==0){
                q.push(num);
            }
        }
    }

    //遍历入度数组，如果出现某个节点的入度不为0，说明存在环，返回空数组
    for(auto num : in){
        if(num!=0){
            ret.clear();
            return ret;
        }
    }

    return ret;
}

int main(){
    return 0;
}